package part2;

import java.util.*;

/**
 * @Author: shaochong
 * @Date: 2021/8/15
 * @Description:
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 *
 * 有效字符串需满足：
 *
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/valid-parentheses
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution20 {
    public static boolean isValid(String s) {

        String left = "({[";
        String right = ")}]";
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        List<Character> stack = new ArrayList();

        for (int i = 0; i < s.length(); i++) {
            if (left.contains(String.valueOf(s.charAt(i)))) {
                stack.add(s.charAt(i));
            } else {
                Character top = stack.size() > 0 ? stack.get(stack.size() - 1) : null;
                Character t = map.get(s.charAt(i));
                if (top == null || t != top) {
                    return false;
                }
                stack.remove(stack.size() - 1);
            }
        }
        return stack.size() == 0;
    }


    // 优化使用双端队列,代替list
    public static boolean isValid2(String s) {

        String left = "({[";
        String right = ")}]";
        Map<Character, Character> map = new HashMap<>();
        map.put(')', '(');
        map.put(']', '[');
        map.put('}', '{');

        Deque<Character> queue = new LinkedList<>();

        for (int i = 0; i < s.length(); i++) {
            if (left.contains(String.valueOf(s.charAt(i)))) {
                queue.add(s.charAt(i));
            } else {
                // 避免使用removeLast,在为空时remvoeLast抛出异常,pollLast返回null
                Character top = queue.pollLast();
                Character t = map.get(s.charAt(i));
                if (top == null || t != top) {
                    return false;
                }
            }
        }
        return queue.size() == 0;
    }



    public static void main(String[] args) {
        String s = "]";
        System.out.println(isValid2(s));
    }


}
